SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Parallel array</title>

</head>

Parallel array

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Computing" title="Computing">computing</a>, a group of parallel arrays (also known as <a href="Structure_of_arrays" class="mw-redirect" title="Structure of arrays">structure of arrays</a> or SoA) is a form of <a href="Implicit_data_structure" title="Implicit data structure">implicit data structure</a> that uses multiple <a href="Array_data_structure" class="mw-redirect" title="Array data structure">arrays</a> to represent a singular array of <a href="Record_(computer_science)" title="Record (computer science)">records</a>. It keeps a separate, homogeneous data array for each field of the record, each having the same number of elements. Then, objects located at the same index in each array are implicitly the fields of a single record. Pointers from one object to another are replaced by array indices. This contrasts with the normal approach of storing all fields of each record together in memory (also known as <a href="Array_of_structures" class="mw-redirect" title="Array of structures">array of structures</a> or AoS). For example, one might declare an array of 100 names, each a string, and 100 ages, each an integer, associating each name with the age that has the same index.

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

An example in <a href="C_(programming_language)" title="C (programming language)">C</a> using parallel arrays:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>int ages[] = {0, 17, 2, 52, 25};

char *names[] = {"None", "Mike", "Billy", "Tom", "Stan"};

int parent[] = {0 /*None*/, 3 /*Tom*/, 1 /*Mike*/, 0 /*None*/, 3 /*Tom*/};

for (i = 1; i <= 4; i++) {

printf("Name: %s, Age: %d, Parent: %s \n",

names[i], ages[i], names[parent[i]]);

}

</pre></div>

in <a href="Perl" title="Perl">Perl</a> (using a hash of arrays to hold references to each array):

<div class="mw-highlight mw-highlight-lang-perl mw-content-ltr" dir="ltr"><pre>my %data = (

first_name => ['Joe', 'Bob', 'Frank', 'Hans' ],

last_name => ['Smith','Seger','Sinatra','Schultze'],

height_in_cm => [169, 158, 201, 199 ]);

for $i (0..$#{$data{first_name}}) {

printf "Name: %s %s\n", $data{first_name}[$i], $data{last_name}[$i];

printf "Height in CM: %i\n", $data{height_in_cm}[$i];

}

</pre></div>

Or, in <a href="Python_Programming_Language" class="mw-redirect" title="Python Programming Language">Python</a>:

<div class="mw-highlight mw-highlight-lang-python3 mw-content-ltr" dir="ltr"><pre>first_names = ["Joe", "Bob", "Frank", "Hans" ]

last_names = ["Smith","Seger","Sinatra","Schultze"]

heights_in_cm = [169, 158, 201, 199 ]

for i in range(len(first_names)):

print("Name: %s %s" % (first_names[i], last_names[i]))

print("Height in cm: %s" % heights_in_cm[i])

# Using zip:

for first_name, last_name, height_in_cm in zip(first_names, last_names, heights_in_cm):

print(f"Name: {first_name} {last_name}")

print(f"Height in cm: {height_in_cm}")

</pre></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

Parallel arrays have a number of practical advantages over the normal approach:

<ul><li>They can save a substantial amount of space in some cases by avoiding alignment issues. For example, some architectures work best if 4-byte integers are always stored beginning at memory locations that are multiple of 4. If the previous field was a single byte, 3 bytes might be wasted. Many modern compilers can automatically avoid such problems, though in the past some programmers would explicitly declare fields in order of decreasing alignment restrictions.</li>

<li>If the number of items is small, array indices can occupy significantly less space than full pointers, particularly on some architectures.</li>

<li>Sequentially examining a single field of each record in the array is very fast on modern machines, since this amounts to a linear traversal of a single array, exhibiting ideal <a href="Locality_of_reference" title="Locality of reference">locality of reference</a> and cache behaviour.</li>

<li>They may allow efficient processing with <a href="SIMD_instruction" class="mw-redirect" title="SIMD instruction">SIMD instructions</a> in certain <a href="Instruction_set_architecture" title="Instruction set architecture">instruction set architectures</a></li></ul>

Several of these advantages depend strongly on the particular programming language and implementation in use.

However, parallel arrays also have several strong disadvantages, which serves to explain why they are not generally preferred:

<ul><li>They have significantly worse <a href="Locality_of_reference" title="Locality of reference">locality of reference</a> when visiting the records non-sequentially and examining multiple fields of each record, because the various arrays may be stored arbitrarily far apart.</li>

<li>They obscure the relationship between fields of a single record (e.g. no type information relates the index between them, an index may be used erroneously).</li>

<li>They have little direct language support (the language and its syntax typically express no relationship between the arrays in the parallel array, and cannot catch errors).</li>

<li>Since the bundle of fields is not a "thing", passing it around is tedious and error-prone. For example, rather than calling a function to do something to one record (or structure or object), the function must take the fields as separate arguments. When a new field is added or changed, many parameter lists must change, where passing objects as whole would avoid such changes entirely.</li>

<li>They are expensive to grow or shrink, since each of several arrays must be reallocated. Multi-level arrays can ameliorate this problem, but impacts performance due to the additional <a href="Indirection" title="Indirection">indirection</a> needed to find the desired elements.</li>

<li>Perhaps worst of all, they greatly raise the possibility of errors. Any insertion, deletion, or move must always be applied consistently to all of the arrays, or the arrays will no longer be synchronized with each other, leading to bizarre outcomes.</li></ul>

The bad locality of reference can be alleviated in some cases: if a structure can be divided into groups of fields that are generally accessed together, an array can be constructed for each group, and its elements are records containing only these subsets of the larger structure's fields. (see <a href="Data-oriented_design" title="Data-oriented design">data-oriented design</a>). This is a valuable way of speeding up access to very large structures with many members, while keeping the portions of the structure tied together. An alternative to tying them together using array indexes is to use <a href="Reference_(computer_science)" title="Reference (computer science)">references</a> to tie the portions together, but this can be less efficient in time and space.

Another alternative is to use a single array, where each entry is a record structure. Many language provide a way to declare actual records, and arrays of them. In other languages it may be feasible to simulate this by declaring an array of n*m size, where m is the size of all the fields together, packing the fields into what is effectively a record, even though the particular language lacks direct support for records. Some <a href="Compiler_optimization" class="mw-redirect" title="Compiler optimization">compiler optimizations</a>, particularly for <a href="Vector_processor" title="Vector processor">vector processors</a>, are able to perform this transformation automatically when arrays of structures are created in the program.

<ul><li><a href="Linked_list#Linked_lists_using_arrays_of_nodes" title="Linked list">An example in the linked list article</a></li>

<li><a href="Column-oriented_DBMS" class="mw-redirect" title="Column-oriented DBMS">Column-oriented DBMS</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><a href="Thomas_H._Cormen" title="Thomas H. Cormen">Thomas H. Cormen</a>, <a href="Charles_E._Leiserson" title="Charles E. Leiserson">Charles E. Leiserson</a>, <a href="Ronald_L._Rivest" class="mw-redirect" title="Ronald L. Rivest">Ronald L. Rivest</a>, and <a href="Clifford_Stein" title="Clifford Stein">Clifford Stein</a>. <a href="Introduction_to_Algorithms" title="Introduction to Algorithms">Introduction to Algorithms</a>, Second Edition. MIT Press and McGraw-Hill, 2001. <style data-mw-deduplicate="TemplateStyles:r1238218222">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03293-7</bdi>. Page 209 of section 10.3: Implementing pointers and objects.</li>

<li><cite id="CITEREFSkeet2014" class="citation web cs1">Skeet, Jon (3 June 2014). <a rel="nofollow" class="external text" href="http://codeblog.jonskeet.uk/2014/06/03/anti-pattern-parallel-collections/">"Anti-pattern: parallel collections"</a>. Retrieved 28 October 2014.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-17" href="https://en.wikipedia.org/wiki/?title=Parallel_array&oldid=1263647666">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>